import java.util.Stack;

/**
 * 剑指 Offer 30. 包含min函数的栈（与 155 同）
 * https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
 */
public class Solutions_Offer_30 {
    public static void main(String[] args) {
        MinStack2 minStack = new MinStack2();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int res1 = minStack.min();  // output: -3
        System.out.println(res1);
        minStack.pop();
        int res2 = minStack.top();  // output: 0
        System.out.println(res2);
        int res3 = minStack.min();  // output: -2
        System.out.println(res3);
    }
}

class MinStack1 {
    private Stack<Integer> stack = null;  // 存储元素
    private Stack<Integer> minStack = null;  // 辅助栈：记录与 stack 中每个元素所对应的最小值

    public MinStack1() {
        stack = new Stack<>();
        minStack = new Stack<>();
        // 给定默认值
        minStack.push(Integer.MAX_VALUE);
    }
    // 将元素 x 入栈
    public void push(int x) {
        stack.push(x);
        // x 与 x 对应的最小值，即栈中的最小元素（对应的最小值只能是先入栈的元素，而不是后入栈）
        minStack.push(Math.min(x, minStack.peek()));
    }
    // 栈顶元素出栈
    public void pop() {
        stack.pop();
        // 同时与其对应的最小值也弹出
        minStack.pop();
    }
    // 获取栈顶元素
    public int top() {
        return stack.peek();
    }
    // 检索栈中的最小元素
    public int min() {
        return minStack.peek();
    }
}

class MinStack2 {
    Node head;

    public MinStack2() {
        head = null;
    }
    // 将元素 x 入栈
    public void push(int x) {
        if (head == null) {
            // 之前没有元素时
            head = new Node();
            head.val = x;
            head.minVal = x;  // 最小值就是本身
        } else {
            Node new_head = new Node();
            new_head.val = x;
            // 将当前元素与前一元素记录的最小值比较
            new_head.minVal = x < head.minVal ? x : head.minVal;
            // 之前添加的元素作为当前元素的下一结点
            new_head.next = head;
            head = new_head;
        }
    }
    // 栈顶元素出栈
    public void pop() {
        // head.next 成为新的栈顶元素
        head = head.next;
    }
    // 获取栈顶元素
    public int top() {
        return head.val;
    }
    // 检索栈中的最小元素
    public int min() {
        return head.minVal;
    }

    public class Node {
        int val;  // 当前结点值
        Node next;  // 下一结点
        int minVal;  // 当前结点对应的最小值
    }
}